#pragma once

// 树结点
template <class K>
struct BSTreeNode
{
    BSTreeNode<K> *_left;
    BSTreeNode<K> *_right;
    K _key;

    BSTreeNode(const K &key)
        : _left(nullptr), _right(nullptr), _key(key)
    {
    }
};

// 二叉搜索树
// K模型
namespace K
{
    template <class K>
    class BSTree
    {
        typedef BSTreeNode<K> Node;

    private:
        Node *_root = nullptr;

    public:
        // 构造函数
        /*
        BSTree()
            :_root(nullptr)
        {

        }
        */
        BSTree() = default; // 强制生成默认构造
        // 拷贝构造
        BSTree(const BSTree<K> &t)
        {
            _root = Copy(t._root);
        }
        // 赋值重载
        // t2 = t1;
        BSTree<K> &operator=(BSTree<K> t)
        {
            // 因为已经实现了拷贝构造 直接拷贝构造参数t
            // 交换后 this->_root指向t的树 t->_root指向t2的树 函数结束t被析构
            swap(_root, t._root);
            return *this;
        }
        // 析构函数
        ~BSTree()
        {
            Destroy(_root);
        }
        // 插入 -- 普通版
        bool Insert(const K &key)
        {
            // 根值插入
            if (_root == nullptr)
            {
                _root = new Node(key);
                return true;
            }

            // 定位合适位置
            Node *parent = nullptr;
            Node *cur = _root;
            while (cur)
            {
                if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    return false;
                }
            }

            cur = new Node(key);
            // 父子链接
            if (parent->_key < key)
            {
                parent->_right = cur;
            }
            else
            {
                parent->_left = cur;
            }

            return true;
        }
        // 插入-递归版
        bool InsertR(const K &key)
        {
            return _InsertR(_root, key);
        }
        // 查找
        bool Find(const K &key)
        {
            Node *cur = _root;
            while (cur)
            {
                if (cur->_key < key)
                {
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    cur = cur->_left;
                }
                else
                {
                    return true;
                }
            }

            return false;
        }
        // 查找-递归版
        bool FindR(const K &key)
        {
            return _FindR(_root, key);
        }
        // 删除
        bool Erase(const K &key)
        {
            Node *cur = _root;
            Node *parent = nullptr;

            while (cur)
            {
                if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                // 找到目标结点--删除
                else
                {
                    // 1、左为空
                    if (cur->_left == nullptr)
                    {
                        // 目标结点为根节点
                        if (cur == _root)
                        {
                            _root = cur->_right;
                        }
                        else
                        {
                            // 目标结点为父节点的左结点
                            if (parent->_left == cur)
                            {
                                // 父左接管目标右
                                parent->_left = cur->_right;
                            }
                            // 目标结点为为父节点的右结点
                            else
                            {
                                // 父右接管目标右
                                parent->_right = cur->_right;
                            }
                        }
                        delete cur;
                    }
                    // 2、右为空
                    else if (cur->_right == nullptr)
                    {
                        // 目标结点为根节点
                        if (cur == _root)
                        {
                            _root = cur->_left;
                        }
                        else
                        {
                            // 目标结点为父节点的左结点
                            if (parent->_left == cur)
                            {
                                // 父左接管目标左
                                parent->_left = cur->_left;
                            }
                            // 目标结点为父节点的左结点
                            else
                            {
                                // 父右接管目标左
                                parent->_right = cur->_left;
                            }
                        }
                        delete cur;
                    }
                    // 3、左右均有子结点
                    else
                    {
                        // 找右树最小节点/左树最大节点
                        // 一、右树最小节点
                        // obj只能是 只有右节点或叶子
                        // 找obj【右树最小结点】
                        // Node* nannyDad = cur;
                        // Node* nanny = cur->_right;
                        // while (nanny->_left)
                        //{
                        //	nannyDad = nanny;
                        //	nanny = nanny->_left;
                        // }
                        ////赋值
                        // cur->_key = nanny->_key;
                        ////obj在父左 obj的右给父左【cur右树第一个结点不为右树最小结点时】
                        // if (nannyDad->_left == nanny)
                        //{
                        //	nannyDad->_left = nanny->_right;
                        // }
                        ////obj在父右 obj的右给父右【cur的右树第一个结点就是右树最小结点时】
                        // else
                        //{
                        //	nannyDad->_right = nanny->_right;
                        // }
                        // delete nanny;

                        // 二、左树最大结点
                        // obj只能是 只有左节点或叶子
                        // 找obj【左树最大结点】
                        Node *nannyDad = cur;
                        Node *nanny = cur->_left;
                        while (nanny->_right)
                        {
                            nannyDad = nanny;
                            nanny = nanny->_right;
                        }
                        // 赋值
                        cur->_key = nanny->_key;

                        // 找到合适的保姆后 把保姆的值给目标结点
                        // 在删除保姆结点之前 要把保姆结点的子树挂接到保姆的父结点上
                        // obj在父左 obj的右给父左
                        if (nannyDad->_left == nanny)
                        {
                            nannyDad->_left = nanny->_left;
                        }
                        // obj在父右 obj的右给父右
                        else
                        {
                            nannyDad->_right = nanny->_left;
                        }
                        delete nanny;
                    }

                    return true;
                }
            }

            return false;
        }

        // 删除-递归版
        bool EraseR(const K &key)
        {
            return _EraseR(_root, key);
        }
        // 中序遍历
        // 1.直接写调用时传_root传不过去 _root是private [可以用GetRoot()]
        // 2._root又无法做缺省值：条件是全局变量 常量 静态变量 且无this指针【this->_root】
        // 类的私有成员无法作为默认参数传递给其他函数 因为这些成员不属于全局作用域、常量或静态变量。
        // 在类的非静态成员函数中 若要使用当前对象的成员变量 必须使用 this 指针
        void InOrder()
        {
            _InOrder(_root);
            cout << endl;
        }

    protected:
        // 拷贝函数
        Node *Copy(Node *root)
        {
            if (root == nullptr)
                return nullptr;

            Node *newRoot = new Node(root->_key);
            newRoot->_left = Copy(root->_left);
            newRoot->_right = Copy(root->_right);
            return newRoot;
        }
        // 销毁函数
        void Destroy(Node *&root)
        {
            if (root == nullptr)
                return;

            Destroy(root->_left);
            Destroy(root->_right);

            delete root;
            root = nullptr;
        }
        // 查找-递归版
        bool _FindR(Node *root, const K &key)
        {
            if (root == nullptr)
                return false;

            if (root->_key == key)
                return true;

            if (root->_key < key)
                return _FindR(root->_right, key);
            else
                return _FindR(root->_left, key);
        }
        // 插入-递归版
        bool _InsertR(Node *&root, const K &key)
        {
            if (root == nullptr)
            {
                // 引用传参 root是上层root的left或right 直接链接 yyds
                root = new Node(key);
                return true;
            }

            if (root->_key < key)
            {
                return _InsertR(root->_right, key);
            }
            else if (root->_key > key)
            {
                return _InsertR(root->_left, key);
            }
            else
            {
                return false;
            }
        }
        // 删除-递归版
        bool _EraseR(Node *&root, const K &key)
        {
            if (root == nullptr)
                return false;

            if (root->_key < key)
            {
                return _EraseR(root->_right, key);
            }
            else if (root->_key > key)
            {
                return _EraseR(root->_left, key);
            }
            // 相等--删除
            else
            {
                // 记录root
                Node *obj = root;
                // 右为空
                if (root->_right == nullptr)
                {
                    root = root->_left; // 实际是上层的root与当前层的root左链接 下同
                }
                // 左为空
                else if (root->_left == nullptr)
                {
                    root = root->_right;
                }
                // 左右都不空
                else
                {
                    // 找到左子树最大结点 【只有左节点或为叶子节点】
                    Node *nanny = root->_left;
                    while (nanny->_right)
                    {
                        nanny = nanny->_right;
                    }
                    swap(root->_key, nanny->_key);
                    // 将找到的nanny与obj进行值交换 然后传新树递归删除值为obj的结点
                    // 此时obj定为叶子节点或只有一个孩子的结点
                    // 利用递归将 删除一个有左右子结点的结点 转换为 删除只有一个结点或删除一个叶子节点

                    // 找到合适的保姆后 把保姆的值给目标结点
                    // 在删除保姆结点之前 要把保姆结点的子树挂接到保姆的父结点上
                    return _EraseR(root->_left, key);
                }
                delete obj;
                return true;
            }
        }

        // 中序遍历
        void _InOrder(Node *root)
        {
            if (root == nullptr)
                return;

            _InOrder(root->_left);
            cout << root->_key << " ";
            _InOrder(root->_right);
        }
    };
}

// KV模型
namespace KV
{
    template <class K, class V>
    struct BSTreeNode
    {
        BSTreeNode<K, V> *_left;
        BSTreeNode<K, V> *_right;
        K _key;
        V _value;

        // 构造函数
        BSTreeNode(const K &key, const V &value)
            : _left(nullptr), _right(nullptr), _key(key), _value(value)
        {
        }
    };

    template <class K, class V>
    class BSTree
    {
        typedef BSTreeNode<K, V> Node;

    public:
        // 插入
        bool Insert(const K &key, const V &value)
        {
            if (_root == nullptr)
            {
                _root = new Node(key, value);
                return true;
            }

            Node *parent = nullptr;
            Node *cur = _root;
            while (cur)
            {
                if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    return false;
                }
            }

            cur = new Node(key, value);
            // 链接
            if (parent->_key < key)
            {
                parent->_right = cur;
            }
            else
            {
                parent->_left = cur;
            }

            return true;
        }
        // 查找
        Node *Find(const K &key)
        {
            Node *cur = _root;
            while (cur)
            {
                if (cur->_key < key)
                {
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    cur = cur->_left;
                }
                else
                {
                    return cur;
                }
            }

            return nullptr;
        }
        // 删除
        bool Erase(const K &key)
        {
            Node *cur = _root;
            Node *parent = nullptr;

            while (cur)
            {
                if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                // 找到目标结点--删除
                else
                {
                    // 1、左为空
                    if (cur->_left == nullptr)
                    {
                        // 目标结点为根节点
                        if (cur == _root)
                        {
                            _root = cur->_right;
                        }
                        else
                        {
                            // 目标结点为左结点
                            if (parent->_left == cur)
                            {
                                // 父左接管目标右
                                parent->_left = cur->_right;
                            }
                            // 目标结点为右结点
                            else
                            {
                                // 父右接管目标右
                                parent->_right = cur->_right;
                            }
                        }
                        delete cur;
                    }
                    // 2、右为空
                    else if (cur->_right == nullptr)
                    {
                        // 目标结点为根节点
                        if (cur == _root)
                        {
                            _root = cur->_left;
                        }
                        else
                        {
                            // 父左接管目标左
                            if (parent->_left == cur)
                            {
                                parent->_left = cur->_left;
                            }
                            // 父右接管目标左
                            else
                            {
                                parent->_right = cur->_left;
                            }
                        }
                        delete cur;
                    }
                    // 3、左右均有子结点
                    else
                    {
                        // 找右树最小节点/左树最大节点
                        // 一、右树最小节点
                        // obj只能是 只有右节点或叶子
                        // 找obj【右树最小结点】
                        // Node* nannyDad = cur;
                        // Node* nanny = cur->_right;
                        // while (nanny->_left)
                        //{
                        //	nannyDad = nanny;
                        //	nanny = nanny->_left;
                        // }
                        ////赋值
                        // cur->_key = nanny->_key;
                        ////obj在父左 obj的右给父左
                        // if (nannyDad->_left == nanny)
                        //{
                        //	nannyDad->_left = nanny->_right;
                        // }
                        ////obj在父右 obj的右给父右
                        // else
                        //{
                        //	nannyDad->_right = nanny->_right;
                        // }
                        // delete nanny;
                        // 二、左树最大结点
                        // obj只能是 只有左节点或叶子
                        // 找obj【左树最大结点】
                        Node *nannyDad = cur;
                        Node *nanny = cur->_left;
                        while (nanny->_right)
                        {
                            nannyDad = nanny;
                            nanny = nanny->_right;
                        }
                        // 赋值
                        cur->_key = nanny->_key;
                        // obj在父左 obj的右给父左
                        if (nannyDad->_left == nanny)
                        {
                            nannyDad->_left = nanny->_left;
                        }
                        // obj在父右 obj的右给父右
                        else
                        {
                            nannyDad->_right = nanny->_left;
                        }
                        delete nanny;
                    }
                    return true;
                }
            }
            return false;
        }

        // 中序遍历
        void InOrder()
        {
            _InOrder(_root);
            cout << endl;
        }

    protected:
        // 中序遍历
        void _InOrder(Node *root)
        {
            if (root == nullptr)
                return;

            _InOrder(root->_left);
            cout << root->_key << ":" << root->_value << endl;
            _InOrder(root->_right);
        }

    private:
        Node *_root = nullptr;
    };
}